package 强化训练;

import java.util.Arrays;
import java.util.Scanner;

public class day14幸运的袋子 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);//将数组按照升序的排列
        int help = help(arr, n, 0, 0, 1);
        System.out.println(help);
    }

    /**
     * 传入数组通过 DFS + 回溯 + 剪枝 返回幸运袋子的个数
     * @param arr 保存球的编号
     * @param n 球的个数
     * @param pos 当前位置
     * @param sum 当前位置 + 前面球编号的和
     * @param multi 当前位置 * 前面编号的积
     * @return 返回幸运袋子的个数
     */
    private static int help(int[] arr,int n,int pos,int sum,int multi){
        int count = 0; //幸运袋子的个数，
        for (int i = pos; i < n; i++) {
            sum += arr[i];
            multi *= arr[i];
            if (sum > multi){
                //如果当前位置的可以组合成幸运的袋子，count + 1 以后，在判断从当前位置出发下一个位置是否可以组合成幸运的袋子
                count = count + 1 + help(arr,n,i+1,sum,multi);
            }else if (arr[i] == 1){
                //如果当前为第一个元素，并且第一个球编号为1，count不加，然后继续判断后的元素
                count = count + help(arr,n,i+1,sum,multi);
            }else {
                break;
            }
            //如果发现了当前位置无法组合幸运的袋子，就继续到下一个位置判断，就需要将sum-不幸运的编号，multi / 不幸运的编号
            sum -= arr[i];
            multi /= arr[i];
            //如果当有多个元素相等，跳过，因为相同编号的球不区别
            while (i < n-1 && arr[i] == arr[i+1]){
                i++;
            }
        }
        //最终所有球都遍历一遍，就结束返回
        return count;
    }
}
